package 算法.LeetCode91.每日打卡题目;

import 算法.NiuKe.ListNode;
import 算法.NiuKe.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: 谢君臣
 * @create: 2021-02-08 20:02
 * @founction: XXXX
 */
public class day09 {
    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode h = head;
        int[] l = new int[]{-10,-3,0,5,9};
        for (int i : l) {
            ListNode node = new ListNode(i);
            h.next = node;
            h = h.next;
        }
        TreeNode treeNode = sortedListToBST(head.next);
    }
    public static TreeNode sortedListToBST(ListNode head) {
        if (head==null)
            return null;
        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        TreeNode root = null;
        root = createNode(root, list, 0, list.size());
        return root;
    }

    private static TreeNode createNode(TreeNode root, List<Integer> list, int L, int R) {
        if (R-L>1){
            int m = (L+R)/2;
            root = new TreeNode(list.get(m));
            root.left = createNode(root.left,list,L,m);
            root.right = createNode(root.right,list,m+1,R);
        }
        if (R-L==1){
            root = new TreeNode(list.get(L));
        }
        return root;
    }

}
